public class text {
    public class ListNode {
    int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 如果两个链表中有一个为空，则返回另外一个
        if(null == list1){
            return list2;
        }
        if(null == list2){
            return list1;
        }
        // 遍历两个链表，将较小的节点往新链表中尾插
        // 为了实现方便，新链表使用带头节点的链表
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        // 只要两个链表都不为空，从前往后遍历
        // 将小的尾插到tail之后
        while(null != cur1 && null != cur2){
            if(cur1.val <= cur2.val){
                tail.next = cur1;
                cur1 = cur1.next;
            }else{
                tail.next = cur2;
                cur2 = cur2.next;
            }
            tail = tail.next;
        }
        // while结束之后，肯定有一个链表先走到末尾
        // 将另外一个不空的链表直接连接在tail之后
        if(null != cur1){
            tail.next = cur1;
        }else{
            tail.next = cur2;
        }
        return newHead.next;
    }
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        boolean isCross=false;
        while(null != fast && null != fast.next){
            fast = fast.next.next;
            slow = slow.next;
            // 如果快慢指针相遇，说明有环
            if(fast == slow){
                isCross = true;
                break;
            }
        }
        if(isCross==false){
            return null;
        }
        ListNode pH = head;    // 从头开始
        ListNode pM = fast;    // 从相遇点开始

        // 两个指针每次都走1步，相遇点就是环的入口
        while(pH != pM){
            pH = pH.next;
            pM = pM.next;
        }

        return pH;
    }
    public ListNode getMiddleNode(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        // fast != null 为了保证fast第一步可以走成功
        // fast.next ！= null 为了保证fast的第二步可以走成功

        // prev保存slow的前一个
        ListNode prev = null;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            prev = slow;
            slow = slow.next;
        }

        //if(fast == null){
        //return prev;
        //}

        return slow;
    }

    public ListNode reverseList(ListNode head){
        ListNode cur = head;
        ListNode prev = null;
        ListNode next = null;

        while(cur != null){
            next = cur.next;

            cur.next = prev;
            prev = cur;
            cur = next;
        }

        return prev;
    }

    public boolean chkPalindrome(ListNode A) {
        // 1. 找A链表的中间节点
        ListNode mid = getMiddleNode(A);
        ListNode B = mid.next;
        mid.next = null;

        // 2. 对B链表进行逆置
        B = reverseList(B);

        // 3 对A和B两个链表从前往后逐个节点进行比对
        ListNode curA = A;
        ListNode curB = B;
        boolean ret = true;
        // A链表
        // B链表
        while(curB != null){
            if(curA.val != curB.val){
                ret = false;
                break;
            }

            curA = curA.next;
            curB = curB.next;
        }

        B = reverseList(B);
        mid.next = B;
        return ret;
    }
}
